import collections
import heapq
from typing import List


class Solution:
    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:
        # 构造无向加权图的邻接列表结构
        graph = collections.defaultdict(dict)
        for edge in paths:
            if edge[1] not in graph[edge[0]] or edge[2] < graph[edge[0]][edge[1]]:
                graph[edge[0]][edge[1]] = edge[2]
                graph[edge[1]][edge[0]] = edge[2]

        visited = {(start, 0): 0}
        cache = {}

        # Dijkstra算法
        heap = [(0, start, 0)]
        while heap:
            mark, n1, power = heapq.heappop(heap)

            if (n1, power) in cache:
                continue

            cache[(n1, power)] = mark

            # print(n1, power, ":", mark)

            # 继续在当前位置充电
            if power < cnt:
                if (n1, power + 1) not in visited or visited[(n1, power + 1)] > mark + charge[n1]:
                    # print((n1, power), "->", (n1, power + 1))
                    heapq.heappush(heap, (mark + charge[n1], n1, power + 1))

            # 移动到其他城市
            for n2, c in graph[n1].items():
                if power >= c:
                    if (n2, power - c) not in visited or visited[(n2, power - c)] > mark + c:
                        # print((n1, power), "->", (n2, power - c))
                        heapq.heappush(heap, (mark + c, n2, power - c))

        return cache[(end, 0)]


if __name__ == "__main__":
    # 43
    print(Solution().electricCarPlan(
        paths=[[1, 3, 3], [3, 2, 1], [2, 1, 3], [0, 1, 4], [3, 0, 5]],
        cnt=6, start=1, end=0,
        charge=[2, 10, 4, 1]))

    # 38
    print(Solution().electricCarPlan(
        paths=[[0, 4, 2], [4, 3, 5], [3, 0, 5], [0, 1, 5], [3, 2, 4], [1, 2, 8]], cnt=8, start=0, end=2,
        charge=[4, 1, 1, 3, 2]))

    # 测试用例22/63 : 578  (存在重复边)
    print(Solution().electricCarPlan(
        paths=[[3, 6, 9], [0, 7, 24], [5, 3, 27], [7, 6, 1], [1, 2, 41], [3, 6, 28], [2, 3, 30], [5, 0, 41], [0, 3, 13],
               [6, 4, 4], [3, 5, 20], [0, 5, 22], [0, 1, 6], [7, 5, 11], [5, 6, 17], [0, 6, 22], [1, 6, 32], [2, 4, 25],
               [0, 7, 34], [0, 4, 36], [3, 0, 25]],
        cnt=43, start=4, end=3,
        charge=[34, 15, 30, 64, 67, 11, 33, 98]
    ))

    # 测试用例25/63 : 3801
    print(Solution().electricCarPlan(
        paths=[[3, 7, 32], [0, 6, 46], [1, 0, 47], [0, 6, 8], [0, 3, 30], [1, 5, 34], [1, 2, 9], [1, 4, 29], [0, 1, 6]],
        cnt=52, start=4, end=5,
        charge=[90, 57, 24, 52, 75, 61, 39, 20]))

    # 测试用例25/63(简化)
    print(Solution().electricCarPlan(
        paths=[[1, 5, 34], [1, 2, 9], [1, 4, 29]],
        cnt=52, start=4, end=5,
        charge=[90, 57, 24, 52, 75, 61, 39, 20]))
